1. Field of the Invention
The present invention relates in general to variable length coders and variable length decoders, and more particularly to a variable length coder for performing entropy coding for video data processed through spatial transformation and motion coding in real-time, and a variable length decoder for performing variable length decoding for the entropy-coded video data from the variable length coder in real-time.
2. Description of the Prior Art
Generally, entropy coding is used for compressing digital video data with no loss. In such an entropy coding technology, variable length coding is adopted in the case where a data generation probability is not fixed. Namely, the variable length coding is used to represent data of the higher generation probability as a shorter code while data of the lower generation probability as a longer code. A Huffman code is well-known as the most effective entropy code.
In the entropy coding technology, source coding is first performed for the digital video data to remove a data redundancy present in a signal source. The digital video data is then entropy-coded by run length coding and the variable length coding.
Then, the source-coded and entropy-coded data is decoded by a variable length decoder.
Referring to FIG. 1, there is shown a block diagram of a conventional variable length coder. As shown in this drawing, the conventional variable length coder comprises a register 7 for storing temporarily data VLi inputted therein, a code generator 10 for generating a codeword VCW and a codelength VCL corresponding to output data from the register 7 and outputting the generated codeword VCW and codelength VCL to registers 8 and 9, respectively, and barrel shifters 5 and 6 for shifting an output codeword from the register 8 and an output codeword from a register 4.
The register 4 is adapted to store temporarily an output codeword from the barrel shifter 6 and output the temporarily stored codeword to the barrel shifters 5 and 6.
Also, the conventional variable length coder comprises a register 3 for storing temporarily an output codeword from the barrel shifter 5 and outputting variable length-coded data VLCo, and a bit operation unit 1 for performing a logical operation for a reset signal RST and output data from a barrel shifter 2 to output an available data signal AVLC and apply bit information VL1 to the barrel shifters 2 and 5.
The barrel shifter 2 is adapted to accumulate an output codelength from the register 9.
The bit operation unit 1 includes a latch 14, flags 15-18, an OR gate OR1, a NOR gate NOR1 and an AND gate AN1. The code generator 10 is comprised of an uncoded-word table 11 of an AND-plane and a codeword table 12 and a codelength table 13 of OR-planes. The uncoded-word table 11, the codeword table 12 and the codelength table 13 are programmed logic arrays (PLAs), respectively.
Referring to FIG. 6, there is shown a block diagram of a conventional variable length decoder. As shown in this drawing, the conventional variable length decoder comprises an interface circuit 609 for arranging and shifting data Vi compressed into a variable length code, inputted therein to designate a codeword to be decoded, and a decoding circuit 610 for comparing the designated codeword from the interface circuit 609 with codeword information stored therein, applying length information of the designated codeword from the interface circuit 609 to the interface circuit 609 in accordance with the compared result and outputting a decoded word V0-V3 corresponding to the designated codeword from the interface circuit 609 in accordance with the compared result.
The interface circuit 609 includes a latch circuit 601 for inputting the data Vi through a buffer B1 and latching the inputted data Vi, a barrel shifter 602 for forming a 16-bit window I0-I15 according to output data VL0 and VL1 from the latch circuit 601, and an adder 606 for adding output data VL2 from a latch circuit 607 and a wordlength L0-L3 from the decoding circuit 610 and outputting the resultant data S0 and C0 to the latch circuit 607.
The latch circuit 607 is adapted to latch the output data S0 from the adder 606 to output shift bit information to the barrel shifter 602 and to latch a carry output C0 from the adder 606.
Also, the interface circuit 609 includes a read signal generator 608 for ANDing a clock signal CLK and a carry VL3 from the latch circuit 607 to generate a read signal RD and outputting the generated read signal RD to the buffer B1 and the latch circuit 601.
The decoding circuit 610 includes a codeword storage unit 603 for storing information regarding an output codeword from the barrel shifter 602, a wordlength storage unit 604 for outputting the wordlength L0-L3 according to output data Cw from the codeword storage unit 603, and a decoded word storage unit 605 for outputting the decoded word V0-V3 through a latch L4 according to the output data Cw from the codeword storage unit 603.
The codeword storage unit 603 is a PLA of an AND-plane, and the wordlength storage unit 604 and the decoded word storage unit 605 are PLAs of OR-planes.
The operation of the conventional variable length coder with the above-mentioned construction will hereinafter be described with reference to FIG. 1.
In response to the clock signal CLK and an enable signal EN, the register 7 stores temporarily the inputted data VLi and then outputs it to the code generator 10. The codeword VCW and the codelength VCL corresponding to the output data from the register 7 are determined by the uncoded-word table 11, the codeword table 12 and the codelength table 13 in the code generator 10 and then applied to the registers 8 and 9, respectively.
The codeword temporarily stored in the register 8 is applied to the barrel shifters 5 and 6 in response to the clock signal CLK and the enable signal EN. Each of the barrel shifters 5 and 6 employs a 16-bit sliding window for a 31-bit input. Upon receiving the current codelength from the register 9, the barrel shifter 6 shifts the codeword from the register 8 by the received codelength from the register 9 and outputs the shifted codeword to the register 4. In this case, a rightmost bit of the register 4 becomes a last data bit, thereby causing the data stored in the register 4 to be connected with the subsequently inputted data.
The barrel shifter 5 is controlled by a remaining bits number of the latch 14. The latch 14 functions to store the number of the bits remaining in the register 4. Namely, the remaining bits number of the latch 14 represents the number of the bits of the codeword present in the register 4. The remaining bits of the register 4 are arranged on the basis of the left side by the barrel shifter 5. If the sum of the remaining bits number and the bits number of the current codeword is greater than or equal to 16, 16-bit data to be first coded is applied from the barrel shifter 5 to the register 3.
On the other hand, the combination of the barrel shifter 2 and the latch 14 functions as an accumulator for accumulating a codelength. In the case where the number of the remaining bits in the register 4 is greater than or equal to 16, the right 16 bits of the output data from the barrel shifter 2 become all 0 and the flag 15 is set to 1 indicative of presence of available data. The output data from the latch 14 is applied to the barrel shifter 2 to allow the barrel shifter 2 to function as a rotator. The other 16-bit input to the barrel shifter 2 is connected to "0" for searching for a carry-out condition. Namely, if the right 16 bits of the output data from the barrel shifter 2 are all "0", the carry-out occurs. The left 16 bits of the output data from the barrel shifter 2 represent the number of newly remaining bits in the register 4.
Upon receiving the temporarily stored codelength from the register 9 in response to the clock signal CLK and the enable signal EN, the barrel shifter 6 shifts the inputted codeword by the received codelength and outputs the shifted codeword to the register 4. The barrel shifter 2 accumulates the codelength from the register 9 and outputs the accumulated value as shift information to the bit operation unit 1.
In the bit operation unit 1, the flags 18, 17 and 16 are set in response to the reset signal RST as the codeword is shifted in the above manner. The set flags 18, 17 and 16 are logically operated with the output data from the barrel shifter 2 by the OR gate OR1, the AND gate AN1 and the NOR gate NOR1, respectively. The output data from the OR gate OR1 and the AND gate AN1 are applied to the latch 14 and the output data from the NOR gate NOR1 is applied to the flag 15.
Then, upon receiving the bit information VL1 from the latch 14 as the available data signal AVLC, the flag 15 is set, and the barrel shifter 5 outputs 16-bit variable length-coded data to the register 3. Also in this case, the accumulated codelength value of the barrel shifter 2 is cleared.
As mentioned above, the conventional variable length coder has the three barrel shifters connected in parallel. The use of the three barrel shifters connected in parallel makes the time required in coding a single word constant. However, with the three barrel shifters connected in parallel, the conventional variable length coder has the disadvantage that an operation speed is low in the case where a plurality of words are coded in parallel.
Now, the operation of the conventional variable length decoder with the above-mentioned construction will be described with reference to FIG. 6.
First, the data stream Vi is inputted to the interface circuit 609. In the interface circuit 609, the buffer B1 applies the inputted data Vi to a latch L0 in the latch circuit 601 in the unit of 16 bits under the control of the read signal generator 608. In response to the next clock signal, the latch L0 shifts the existing data to a latch L1 of the latch circuit 601 and inputs the data Vi of new 16 bits. As a result, the latch circuit 601 outputs the latch data VL1 and VL0 of the respective 16 bits to the barrel shifter 602.
Upon receiving the output data VL1 and VL0 from the latches L1 and L0 in the latch circuit 601, the barrel shifter 602 forms the window of bits I0-I15, a leading bit of which is the first bit to be decoded among the received 32 bits. The window from the barrel shifter 602 is shifted by the output data VL2 from the latch circuit 607, resulting in the detection of the codeword. The detected codeword is then applied to the codeword storage unit 603. The codeword storage unit 603 detects the decoded data Cw corresponding to the received codeword and then outputs it to the wordlength storage unit 604 and the decoded word storage unit 605. The wordlength storage unit 604 outputs the wordlength L0-L3 corresponding to the decoded data Cw from the codeword storage unit 603 to the adder 606. The decoded word storage unit 605 outputs the decoded word V0-V3 corresponding to the decoded data Cw from the codeword storage unit 603 through the latch L4.
The adder 606 adds the output data L0-L3 from the wordlength storage unit 604 and the output data VL2 from the latch circuit 607 and outputs the added result as the bit shift information to a latch L2 in the latch circuit 607. The barrel shifter 602 forms the 16-bit window I0-I15 by shifting the output data VL1 and VL0 from the latch circuit 601 by the output data VL2 from the latch L2 in the latch circuit 607.
On the other hand, if the wordlength value accumulated by the adder 606 exceeds 16 in decoding, a latch L3 of the latch circuit 607 outputs the carry VL3 to the read signal generator 608. In the read signal generator 608, an AND gate AN11 ANDs the clock signal CLK and the carry VL3 from the latch circuit 607 and outputs the ANDed result as the read signal RD to the buffer B1 and the latch L0 of the latch circuit 601. As a result, the buffer B1 outputs the data Vi of new 16 bits to the latch L0 of the latch circuit 601.
The operation of the conventional variable length decoder will hereinafter be described in more detail with reference to FIGS. 7 and 8. FIG. 7 is a view illustrating an example of the wordlengths and codewords of the data used in the conventional variable length decoder of FIG. 6, and FIG. 8 is a view illustrating an example of the decoding operation of the conventional variable length decoder of FIG. 6.
In the case where the data as shown in FIG. 8 are latched by the latches L1 and L0, the first 2 bits of the window of the barrel shifter 602 are recognized as a symbol b and applied to the codeword storage unit 603 in response to the first clock signal. Then, upon receiving the wordlength "2" from the wordlength storage unit 604, the adder 606 adds the received wordlength "2" to an initial value "0" and outputs the resultant value "2" to the latch L2. The output data "2" from the latch L2 causes the window of the barrel shifter 602 to be shifted by "2" to the right. On the other hand, the decoded word storage unit 605 outputs the decoded word V0-V3 corresponding to the codeword matched in the codeword storage unit 603.
In response to the second clock signal, the subsequent 5 bits of the window of the barrel shifter 602 are recognized as a symbol g and applied to the codeword storage unit 603. Then, upon receiving the wordlength "5" from the wordlength storage unit 604, the adder 606 adds the received wordlength "5" to the previous value "2" and outputs the resultant value "7" to the latch L2. The output value "7" from the latch L2 causes the window of the barrel shifter 602 to be shifted by "7" to the right.
If the wordlength value accumulated by the adder 606 exceeds 16 in operation, the carry VL3 is generated in the latch L3 of the latch circuit 607 and applied to the read signal generator 608. In the read signal generator 608, the AND gate AN11 ANDs the clock signal CLK and the carry VL3 from the latch circuit 607 and outputs the ANDed result as the read signal RD to the buffer B1 and the latch L0 of the latch circuit 601. As a result, the buffer B1 outputs the data Vi of new 16 bits to the latch L0 of the latch circuit 601. Then, the above operation is repeatedly performed on the basis of the data Vi of the new 16 bits.
It should be noted that, in the above-mentioned conventional variable length decoder, the time required in the decoding is one cycle regardless of the length of the codeword, which is the sum of the delay time of the latch L0, the shifting delay time of the barrel shifter 602, the matching delay time of the codeword and the addition time of the adder 606. For this reason, the conventional variable length decoder has the disadvantage that the decoding time is fixed regardless of the length of the codeword. Also, although the data is transmitted at a high bit rate, the operation of accumulating the length of the matched codeword may be delayed. This causes the decoding not to be performed in real-time.